package com.zrf.base.knowledge.leetcode.editor.cn;

/**
 * //给你一个升序排列的整数数组 nums ，和一个整数 target 。
 * //
 * // 假设按照升序排序的数组在预先未知的某个点上进行了旋转。（例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
 * //
 * // 请你在数组中搜索 target ，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。
 * //
 * //
 * // 示例 1：
 * //
 * //
 * //输入：nums = [4,5,6,7,0,1,2], target = 0
 * //输出：4
 * //
 * //
 * // 示例 2：
 * //
 * //
 * //输入：nums = [4,5,6,7,0,1,2], target = 3
 * //输出：-1
 * //
 * // 示例 3：
 * //
 * //
 * //输入：nums = [1], target = 0
 * //输出：-1
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= nums.length <= 5000
 * // -10^4 <= nums[i] <= 10^4
 * // nums 中的每个值都 独一无二
 * // nums 肯定会在某个点上旋转
 * // -10^4 <= target <= 10^4
 * //
 * // Related Topics 数组 二分查找
 * // 👍 1030 👎 0
 *
 * @author zhouruifeng
 * @date 2020-10-25 11:03:28
 */
public class SearchInRotatedSortedArray {
    public static void main(String[] args) {
        Solution solution = new SearchInRotatedSortedArray().new Solution();
        System.out.println(solution.search(new int[]{5, 1, 3}, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int search(int[] nums, int target) {
            return search(nums, target, 0, nums.length - 1);
        }

        private int search(int[] nums, int target, int start, int end) {
            if (end - start <= 1) {
                if (nums[start] == target) {
                    return start;
                } else if (nums[end] == target) {
                    return end;
                } else {
                    return -1;
                }
            }
            int midIndex = (start + end) / 2;
            if (nums[start] > nums[end]) {
                if (target == nums[midIndex]) {
                    return midIndex;
                }
                if (nums[start] < nums[midIndex]) {
                    if (target >= nums[start] && target < nums[midIndex]) {
                        return search(nums, target, start, midIndex - 1);
                    } else {
                        return search(nums, target, midIndex + 1, end);
                    }
                } else {
                    if (target > nums[midIndex] && target <= nums[end]) {
                        return search(nums, target, midIndex + 1, end);
                    } else {
                        return search(nums, target, start, midIndex - 1);
                    }
                }
            } else {
                //二分
                if (target == nums[midIndex]) {
                    return midIndex;
                } else if (target < nums[midIndex]) {
                    return search(nums, target, start, midIndex - 1);
                } else {
                    return search(nums, target, midIndex + 1, end);
                }
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}